package com.ample16.stackdemo.algorithm;

import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 二叉树层遍历
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write code here
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        linkedList.add(root);
        while (!linkedList.isEmpty()) {
            ArrayList<Integer> subList = new ArrayList<>();
            int count = linkedList.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = linkedList.poll();
                subList.add(node.val);
                if (Objects.nonNull(node.left)) {
                    linkedList.add(node.left);
                }
                ;
                if (Objects.nonNull(node.right)) {
                    linkedList.add(node.right);
                }
                ;
            }
            list.add(subList);
        }
        return list;
    }

    /**
     * 列表反转
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode pre=null;
        while (head != null) {
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

    /**
     * 跳台阶:f(n)=f(n-1)+f(n-2)
     * @param target
     * @return
     */
    public int jumpFloor(int target) {
        if(target==1){
            return 1;
        }
        if(target==2){
            return 2;
        }
        if(target>=3){
            return jumpFloor(target-1)+jumpFloor(target-2);
        }
        throw new RuntimeException("错误的参数值");
    }

    /**
     * 字符串原地反转,双指针
     * @param str
     * @return
     */
    public String reverseStr(String str){
        char[] chars = str.toCharArray();
        int left=0;
        int right=chars.length-1;
        while (left<right){
            char temp=chars[left];
            chars[left]=chars[right];
            chars[right]=temp;
            left++;
            right--;
        }
        return new String(chars);
    }

    public void test(){
        Stack<Integer> stack1 = new Stack<>();
    }
}